package leetcode.linkedlist;


/**
 * 21. 合并两个有序链表
 *
 * 相似题目
 * 88. 合并两个有序数组
 *
 */
public class MergeTwoLists {

    public static void main(String[] args) {
        MergeTwoLists solution = new MergeTwoLists();
        Integer[] arr1 = {-9,3};
        Integer[] arr2 = {5,7};
        ListNode l1 = ListNode.makeLinkedList(arr1);
        ListNode l2 = ListNode.makeLinkedList(arr2);

        ListNode resList = solution.mergeTwoLists(l1,l2);
        System.out.println(resList);
    }


    /**
     * 使用双指针比较两数大小, 插入法构建新的链表 (自己写的)
     *
     * 迭代法 创建新的节点, 不改变原始链表
     *
     * @param list1 链表1
     * @param list2 链表2
     * @return
     */
    public ListNode mergeTwoLists0(ListNode list1, ListNode list2) {
        ListNode head = new ListNode(0);
        ListNode tail = head;

        while (list1 != null && list2 != null) {
            int v1 = list1.val;
            int v2 = list2.val;
            if (v1 < v2) {
                tail.next = new ListNode(v1);
                list1 = list1.next;
            } else {
                tail.next = new ListNode(v2);
                list2 = list2.next;
            }
            tail = tail.next;
        }

        while (list1 != null) {
            tail.next = new ListNode(list1.val);
            list1 = list1.next;
            tail = tail.next;
        }

        while (list2 != null) {
            tail.next = new ListNode(list2.val);
            list2 = list2.next;
            tail = tail.next;
        }
        return head.next;
    }


    /**
     * 迭代法 (官方推荐)
     * 直接使用原始两个链表的节点
     *
     * @param l1    链表1
     * @param l2    链表2
     * @return
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);

        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                // 新链表的最后一个节点的next指针指向头节点较小的链表的头节点
                prev.next = l1;
                // 头节点较小的链表的指针后移一位
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }



    /**
     * 使用递归 合并两个有序链表
     * 较小结点的 next 指针指向其余结点的合并结果
     *
     * @param l1    链表1
     * @param l2    链表2
     * @return
     */
    public ListNode mergeTwoLists1(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

}
